
/**
 * 数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
 * 给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
 */

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 暴力查找，内存，时间超出限制
// var smallestDistancePair = function (nums, k) {
//   let n = nums.length
//   const res = []
//   for (let i = 0; i < n - 1; i++) {
//     for (let j = i + 1; j < n; j++) {
//       res.push(Math.abs(nums[i] - nums[j]))
//     }
//   }
//   return res.sort((a, b) => {
//     return a - b
//   })[k - 1]
// };

// console.log(smallestDistancePair([1, 1, 1], 2));
// smallestDistancePair([1, 5, 8, 2], 3)

// 二分查找
// var smallestDistancePairTs = function (nums: [number], k: number): number {
//   nums.sort()
//   // 最大差距 =  nums[n - 1] - nums[0]
//   let n = nums.length, left = 0, right = nums[n - 1] - nums[0]
//   while (left <= right) {
//     const mid = Math.floor((right + left) / 2)
//     let cnt = 0
//     for (let j = 0; j < n; j++) {
//       const i = binarySearch(nums, j, nums[j] - mid)
//       cnt += j - i
//     }
//     if (cnt >= k) {
//       right = mid - 1
//     } else {
//       left = mid + 1
//     }
//   }
//   return left
// }

// const binarySearchTs = function (nums: number, end: number, target: number): number {
//   debugger
//   let left = 0, right = end;
//   while (left < right) {
//     const mid = Math.floor((left + right) / 2)
//     if (nums[mid] < target) {
//       left = mid + 1
//     } else {
//       right = mid
//     }
//   }
//   return left
// }

// 二分 + 双指针
var smallestDistancePaiTs = function (nums, k) {
  nums.sort((a, b) => a - b);
  let n = nums.length, left = 0, right = nums[n - 1] - nums[0];
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    let cnt = 0;
    for (let i = 0, j = 0; j < n; j++) {
      while (nums[j] - nums[i] > mid) {
        i++;
      }
      cnt += j - i;
    }
    if (cnt >= k) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
}
